# 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
#  每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
#       如果 x == y，那么两块石头都会被完全粉碎；
#       如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
#  最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
#
#  示例 1：
# 输入：stones = [2,7,4,1,8,1]
# 输出：1
# 解释：
# 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
# 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
# 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
# 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
#
#  示例 2：
# 输入：stones = [31,26,33,21,40]
# 输出：5
from typing import List


class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        """
        题目如果换种说法就简单了：stones = [2,7,4,1,8,1]，在每一个数字前添加+或-，使式子的绝对值最小。就可以转化成LeetCode494了
        这意味我们最终得到的结果，可以为原来 stones 数组中的数字添加 +/− 符号(即将stones分成两堆(正/负号堆))，所形成的「计算表达式」所表示。
        问题就被转换为：为 stones 中的每个数字添加 +/−，使得形成的「计算表达式」结果绝对值最小
        再进一步，假设stones的数组和为sum，假设要添-的数字的和为neg，那么最后要求（sum - neg） - neg的绝对值最小，就变成了01背包问题
        再进一步,由于想要「计算表达式」结果绝对值，因此我们需要将石子划分为差值最小的两个堆
        即是说从 stones 数组中选择，凑成总和不超过 sum // 2 的最大价值。

        为什么可以不考虑有放回的石子呢？
            其实所谓的「有放回」操作，只是触发调整「某个原有石子」所在「哪个堆」中，并不会真正意义上的产生「新的石子重量」
            假设有起始石子 a 和 b，且两者重量关系为 a >= b，那么首先会将 a 放入「正号堆」，将 b 放入「负号堆」。
            重放回操作可以看作产生一个新的重量为 a−b 的“虚拟石子”，将来这个“虚拟石子”也会参与某次合并操作，也会被添加 +/− 符号：
                当对“虚拟石子”添加 + 符号，即可 +(a - b)，展开后为 a - b，即起始石子 a 和 b 所在「石子堆」不变
                当对“虚拟石子”添加 − 符号，即可 -(a - b)，展开后为 b - a，即起始石子 a 和bb 所在「石子堆」交换
            因此所谓不断「合并」&「重放」，本质只是在构造一个折叠的计算表达式，最终都能展开扁平化为非折叠的计算表达式。
        :param stones:
        :return:
        """
        total = sum(stones)
        targetSum, stoneSize, res = total // 2, len(stones), 0
        # dp[i][j] 表示是否存在 在数组 nums 的前 i 个(nums[0:i])数中选取若干元素，使得这些元素之和等于j
        dp = [[False] * (targetSum + 1) for _ in range(len(stones) + 1)]
        dp[0][0] = True
        # 遍历求出所有可能的结果值
        for i in range(1, stoneSize + 1):
            for j in range(targetSum + 1):
                if j < stones[i - 1]:  # j < stones[i - 1] 则 当前值一定不可能被选
                    dp[i][j] = dp[i - 1][j]
                else:  # j >= stones[i - 1] 则 当前值可能不被选，也可能被选，所以只要一个为true即为true
                    dp[i][j] = dp[i - 1][j] or dp[i - 1][j - stones[i - 1]]
        for j in range(targetSum, -1, -1):  # 从后向前遍历得到最小值
            if dp[stoneSize][j]:
                res = total - j * 2
                break
        return res

        # # 空间优化写法：由于当前状态只与上一行有关，所以可以进行空间优化(从后向前直接将上一行的值进行覆盖即可)
        # dp = [False] * (targetSum + 1)
        # dp[0] = True
        # for curStone in stones:
        #     for j in range(targetSum, -1, -1):
        #         if j >= curStone:
        #             dp[j] = dp[j - curStone] or dp[j]
        #     for j in range(targetSum, curStone - 1, -1):
        #         dp[j] = dp[j - curStone] or dp[j]
        # for j in range(targetSum, -1, -1):  # 从后向前遍历得到最小值
        #     if dp[j]:
        #         res = total - j * 2
        #         break
        # return res


if __name__ == "__main__":
    stones = [2, 7, 4, 1, 8, 1]
    stones = [31, 26, 33, 21, 40]
    print(Solution().lastStoneWeightII(stones))
